/*
 * @lc app=leetcode.cn id=93 lang=cpp
 *
 * [93] 复原 IP 地址
 */

// @lc code=start
class Solution
{
private:
    vector<string> res;
    vector<string> path;
    void backtracking(const string &s, int sum, int index)
    {
        //回溯 首先终止条件是划分了四段 且满足条件
        if (sum == 4 && index == s.size())
        {
            string ss = "";
            for (int i = 0; i < 3; i++)
            {
                ss += path[i];
                ss += ".";
            }
            ss += path[3];
            res.push_back(ss);
            return;
        }
        //然后是处理本层节点 for循环
        //index代表起始位置 区间设置为左闭右闭区间
        for (int i = index; i < s.size() && i - index < 3; i++)
        {
            //如何选择本层节点 如果距离上一个节点小于等于3 可以选择 否则不能
            //如果当前为0 则必须划分 不能选择后面的
            //如果距离为3 但是数大于255 也不能选
            if (i > index && s[index] == '0')
            {
                break;
            }

            if (i - index == 2)
            {
                string tmp = s.substr(index, 3);
                int x = stoi(tmp);
                if (x > 255)
                {
                    break;
                }
            }
            //现在可以划分了 处理树枝的关系
            path.push_back(s.substr(index, i - index + 1));
            backtracking(s, sum + 1, i + 1);
            path.pop_back();
        }
    }

public:
    vector<string> restoreIpAddresses(string s)
    {
        //实际就是分成四段 也是回溯的思路
        backtracking(s, 0, 0);
        return res;
    }
};
// @lc code=end
